package com.zdp.leetcodeMiddle;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/*
* 题目描述：
* 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
示例 4:
输入: s = ""
输出: 0
提示：
0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class 无重复字符的最长子串_3 {
    public static void main(String[] args) {
        无重复字符的最长子串_3 demo = new 无重复字符的最长子串_3();
        System.out.println(demo.lengthOfLongestSubstring1("abcabcbb"));
    }
    /*
    * 自己的思路就是：
    *  用一个Map 来记录 字符和其出现的位置，同时也用这个Map来作唯一的判断
    * 如何加速这个求解过程？
    * 如果发现重复字符，那么就从重复字符的第一次出现的位置+1开始重新匹配无重复的子串。
    * 为什么如此？ 因为如果从重复字符第一次出现的位置之前开始匹配的话，那么还是会经过这个重复字符，也就是说子串的重复不可避免
    * */
    public int lengthOfLongestSubstring(String s) {
        char[] arr = s.toCharArray();
        Map<Character,Integer> only = new HashMap<>();
        int i =0;
        int count = 0;
        int max = Integer.MIN_VALUE;
        while(i<arr.length){
            if(only.containsKey(arr[i])){
                // 如果重复了，就改变i
                i = only.get(arr[i])+1;
                only.clear();
                max = Math.max(count,max);
                count = 0;
            }else{
                // 如果没有重复
                only.put(arr[i],i);
                i++;
                count++;
            }
        }
        max = Math.max(count,max);
        return max;
    }
    /*
    * Leetcode 题解 ： 使用滑动窗口算法
    * 怎么滑？
    * 他这个大概就是：你目前的子串都是无重复的，那么你左边界那左移动一位，
    * 新的左边界到右边界也是无重复的。
    * eg： 一个无重复的子串头部k 尾部为rk （左边界和右边界）
    * 左边界向右扩 k+1 ,由于 k---rk是无重复的，那么 k+1----rk也是无重复的。
    * 所以可以无需重新判断，直接扩充右边界即可
    * 然后向右扩充右边界
    * 这边的左边界 就是你每个子串的头部
    * */
    public int lengthOfLongestSubstring1(String s) {
        Set<Character> only = new HashSet<>();
        // 左右边界
        int right = -1;
        char[] arr = s.toCharArray();
        int i=0;// i做左边界
        int max = 0;
        while(i<arr.length && right<arr.length){
            // 确定左边界，确定子串的头
            if(i!=0){
                only.remove(arr[i-1]);
            }
            // 右边界往外扩
            while(right+1 < arr.length && !only.contains(arr[right+1])){
                // 不重复就往外扩
                only.add(arr[right+1]);
                right++;
            }
            i++;
            max = Math.max(max,right-i+2);
        }
        return max;
    }
}
